//输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。 
//
// 
//
// 示例 1: 
//
// 输入: [10,2]
//输出: "102" 
//
// 示例 2: 
//
// 输入: [3,30,34,5,9]
//输出: "3033459" 
//
// 
//
// 提示: 
//
// 
// 0 < nums.length <= 100 
// 
//
// 说明: 
//
// 
// 输出结果可能非常大，所以你需要返回一个字符串而不是整数 
// 拼接起来的数字可能会有前导 0，最后结果不需要去掉前导 0 
// 
// Related Topics 贪心 字符串 排序 👍 456 👎 0

package leetcode.editor.offer;

import java.lang.String;
import java.util.HashSet;

// 剑指 Offer 45. 把数组排成最小的数
// https://leetcode.cn/problems/ba-shu-zu-pai-cheng-zui-xiao-de-shu-lcof/
class BaShuZuPaiChengZuiXiaoDeShuLcof {
    public static void main(String[] args) {
        Solution solution = new BaShuZuPaiChengZuiXiaoDeShuLcof().new Solution();
//        solution.minNumber(new int[]{3, 30, 34, 5, 9});
        HashSet<String> set = new HashSet<>();
        set.add("nihao");
        boolean nihao = set.add("nihao");
        System.out.println(nihao);
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 自定义排序比较
         * https://leetcode.cn/problems/ba-shu-zu-pai-cheng-zui-xiao-de-shu-lcof/solution/mian-shi-ti-45-ba-shu-zu-pai-cheng-zui-xiao-de-s-4/
         * @param nums
         * @return
         */
        public String minNumber(int[] nums) {
            String[] array = new String[nums.length];
            for (int i = 0; i < nums.length; i++) {
                array[i] = String.valueOf(nums[i]);
            }
            quickSort(array, 0, array.length - 1);
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < array.length; i++) {
                sb.append(array[i]);
            }
            return sb.toString();
        }

        public void quickSort(String[] array, int l, int r) {
            if (l >= r) {
                return;
            }

            int i = l, j = r;
            while (i < j) {
                while (i < j && (array[j] + array[l]).compareTo(array[l] + array[j]) >= 0) j--;
                while (i < j && (array[i] + array[l]).compareTo(array[l] + array[i]) <= 0) i++;
                swap(array, i, j);
            }
            swap(array, l, i);

            quickSort(array, l, i - 1);
            quickSort(array, i + 1, r);
        }

        public void swap(String[] array, int i, int j) {
            String temp = array[i];
            array[i] = array[j];
            array[j] = temp;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
